Inteligencia Artificial

1 Contenido de la clase

Avisos, asesorías y repaso de complejidad [00:00-04:22]

Se recuerdan los avisos del curso (≈40 inscritos, 45 en Classroom), las dudas de la tarea 1 y la dinámica de entrega: primero se entrega, luego hay un periodo de ~10 días y después se agendan reuniones por correo. Las asesorías se asignan por orden alfabético a cuatro asesores y quedan publicadas en Classroom, con al menos una hora por semana.

Repaso de la complejidad de la búsqueda en anchura: O(V + E) en grafos y O(b^m) en árboles (en árboles E = V − 1, así que V + E = 2V − 1 = O(V)). Queda como comentario la diferencia entre Dijkstra y la búsqueda de costo uniforme: UCS se detiene al extraer la meta de la frontera, Dijkstra calcula el camino más corto del origen a todos los nodos [03:01-04:22].

A\*: costo uniforme + voraz [04:22-06:20]

A\* ordena la búsqueda por la suma de dos componentes: el costo real acumulado y la estimación heurística.

f(n) = g(n) + h(n) [05:05-05:14]

g(n) es el costo real del camino (parte de la búsqueda de costo uniforme) y h(n) es la heurística (parte de la búsqueda voraz). En el ejemplo, al salir de S hacia A la frontera tiene B, E y F: f(B) = 4 + 2 = 6, f(E) = 2 + 6 = 8 y f(G) = 9 + 1 = 10, por lo que se expande B [05:15-06:17].

¿Es A\* óptimo? El contraejemplo [06:20-07:30]

Con una heurística que no ayuda, A\* puede elegir mal: desde F, el camino hacia C parece costar 5 (real 5 + h 0) y el de A parece 7 (real 1 + h 6), así que A\* se va por C; pero el óptimo real es F → A → C = 1 + 3 = 4. La optimalidad de A\* no es automática: depende de las propiedades de la heurística.

Heurísticas admisibles [07:30-08:40]

Una heurística es admisible si nunca sobrestima el costo real que falta. Es una heurística optimista.

0 ≤ h(n) ≤ h*(n) [07:30-07:45]

Donde h\*(n) es el costo verdadero del camino óptimo a la meta más cercana. Si h = 0 para todos los nodos, A\* degenera en la búsqueda de costo uniforme [08:11-08:31].

Demostración de la optimalidad de A\* [20:00-28:44]

Sean A una meta óptima y B una meta subóptima, con h admisible. Si B está en la frontera, algún ancestro n de A también lo está (o A mismo). Como g(A) < g(B) y h(A) = 0, se cumple f(n) ≤ f(A) < f(B): n se expande antes que B, y por inducción todos los ancestros de A se expanden antes que B. Por lo tanto A se expande antes que B y A\* es óptimo. Clave práctica: hay que detenerse al extraer la meta, no basta con que llegue a la frontera [23:51-24:07].

Crear heurísticas: problemas relajados y distancia en línea recta [28:44-41:20]

El diseño de la heurística es el punto más importante al usar A\*. Las buenas heurísticas salen de problemas relajados: la ruta entre ciudades se relaja permitiendo "volar en línea recta"; los problemas con enteros se relajan permitiendo fracciones. A veces una heurística inadmisible sirve cuando basta con encontrar alguna solución.

Para el problema de la ruta más corta entre ciudades, h_SLD(n) = distancia euclidiana de n a la meta. Es admisible porque un camino por carretera recorre al menos la distancia en línea recta: h_SLD(n) ≤ h\*(n) y ≥ 0 [41:00-41:20].

Búsqueda en grafos [41:20-46:20]

Regla de oro: nunca expandir un estado dos veces. La implementación es búsqueda en árbol + un conjunto de estados ya expandidos (cerrados); antes de expandir un nodo se revisa que no se haya expandido antes. Al llevar esta memoria aparece una condición nueva: necesitamos consistencia [41:56-42:05].

Consistencia de heurísticas y desigualdad del triángulo [46:20-49:36]

Además de la admisibilidad (h(v) ≤ h\*(v)), se pide la consistencia (monotonicidad): el cambio de la heurística entre dos nodos no supera el costo del arco.

h(u) − h(v) ≤ d(u, v)  →  h(A) ≤ costo(A→C) + h(C) [46:43-48:15]

Consistencia ⟹ admisibilidad, y con eso A\* sobre grafos es óptimo. La distancia en línea recta es consistente porque cumple la desigualdad del triángulo: d(n, meta) ≤ d(n, n') + d(n', meta) [49:15-49:27].

El algoritmo y comentarios finales [61:20-65:30]

Se maneja un conjunto de cerrados; se inserta el nodo inicial en la frontera y se repite: si la frontera está vacía, no hay solución; se saca el nodo de menor f; si es meta, termina; si no, se añaden sus sucesores y el nodo pasa a cerrados. Comentarios del profesor: no olvidar quitar los nodos ya visitados; el agente no prueba todos los planes en el mundo real — planear es simular; "la búsqueda es tan buena como lo sea el modelo"; y "los errores pasan" [63:40-65:25].

Sudoku y hacia dónde sigue [65:30-68:43]

Se propone resolver un sudoku preguntándose qué algoritmo conviene (anchura, profundidad o A\*). Para la próxima clase: los problemas de satisfacción de restricciones (CSP) [68:35-68:43].

Complementos y precisiones

• A* en grafo y h inconsistente: con h consistente, A* nunca reabre un nodo cerrado; con h solo admisible pero inconsistente hay que reabrir (o guardar el mejor g visto), o A* puede dar una solución subóptima.
• Completitud de A*: es completo si existe solución y los costos de arco son ≥ ε > 0; mantiene todos los nodos en memoria (O(b^d)).
• Dominancia: si h₂(n) ≥ h₁(n) para todo n (ambas admisibles), h₂ domina a h₁ y A* expande ≤ nodos; conviene una h admisible lo más grande posible.
• A* ponderado (weighted A*): f(n) = g(n) + W·h(n) con W > 1; con h inadmisible encuentra solución más rápido a cambio de una cota de suboptimalidad (no cuesta más de W veces la óptima) — satisficing search.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

En la tarea hay dos heurísticas propuestas y hay que demostrar que son admisibles (y de ahí, consistentes) [28:44-28:56].

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

Además, revisar el Classroom del curso para avisos, grupos de asesoría y materiales. [02:20-02:57]

6 Glosario de términos

• Búsqueda informada: usa conocimiento del problema (una heurística) para decidir qué expandir.
• A*: algoritmo informado que expande el nodo con f(n) = g(n) + h(n) mínima.
• g(n): costo real acumulado desde el inicio hasta n.
• h(n): heurística; estimación del costo que falta de n a la meta.
• h*(n): costo real del camino óptimo de n a la meta más cercana.
• Admisibilidad: h no sobrestima: 0 ≤ h(n) ≤ h*(n).
• Consistencia (monotonicidad): h(u) − h(v) ≤ d(u, v) para toda arista (u, v); implica admisibilidad.
• Desigualdad del triángulo: d(n, meta) ≤ d(n, n') + d(n', meta).
• h_SLD: heurística de distancia en línea recta (euclidiana) a la meta.
• Problema relajado: versión con menos restricciones de la que se derivan heurísticas admisibles.
• Búsqueda en árbol vs. en grafo: en grafo se lleva un conjunto de cerrados para no repetir estados.
• Conjunto de cerrados: estados ya expandidos (no admite duplicados).
• Reapertura de nodos: volver a expandir un nodo cerrado al hallar un camino más barato; necesaria si h es inconsistente.
• Dominancia: h₂ domina a h₁ si h₂(n) ≥ h₁(n) para todo n (ambas admisibles); implica expandir ≤ nodos.
• A* ponderado (weighted A*): f(n) = g(n) + W·h(n) con W > 1; más rápido, con cota de suboptimalidad (satisficing).
• CSP: problemas de satisfacción de restricciones; tema de la siguiente clase.

7 Mapa mental textual

• Inteligencia Artificial · Clase 4 — Búsqueda con información
  • A*
    • f(n) = g(n) + h(n)
    • g(n): costo real acumulado
    • h(n): estimación (voraz)
    • Demostración de optimalidad · detenerse al extraer la meta
  • Heurísticas
    • Admisibilidad: 0 ≤ h(n) ≤ h*(n)
    • Consistencia: h(u) − h(v) ≤ d(u, v)
    • Distancia en línea recta (h_SLD)
    • Problemas relajados
  • Búsqueda en grafos
    • No expandir un estado dos veces
    • Conjunto de cerrados
  • Repaso y cierre
    • Complejidad BFS: O(V + E) / O(b^m)
    • Dijkstra vs. costo uniforme
    • Sudoku → próxima clase: CSP